/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/* 
 * Copyright (c) 2009 City University of Hong Kong
 * 
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License m_version 2 as
 * published by the Free Software Foundation;
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 * 
 * Author: Wilson Thong (wilsonwk@ee.cityu.edu.hk) 
 */
#include "ipv4-deflection-routing.h"
#include "bmsn-routing.h"
#include "ns3/net-device.h"
#include "ns3/callback.h"
#include "ns3/queue.h"
#include <iostream>
#include <sstream>

NS_LOG_COMPONENT_DEFINE ("Ipv4DeflectionRouting");

namespace ns3 {
namespace eecityu {

using namespace std;

NS_OBJECT_ENSURE_REGISTERED (Ipv4DeflectionRouting);

/**
 * \brief print out the list of net devices stored in the notDevContainer
 * \param container The container of a set of net devices
 * \return A string representation of all the net devices in the container
 */
string 
PrintNetDeviceContainer (NetDeviceContainer container)
{
  ostringstream os;
  for (uint32_t i = 0;;)
  {
    os << container.Get (i)->GetIfIndex ();
    if (++i < container.GetN ())
      os << ", ";
    else
      break;    
  }
  return os.str ();
}

TypeId 
Ipv4DeflectionRouting::GetTypeId (void)
{
  static TypeId tid = TypeId ("ns3::eecityu::Ipv4DeflectionRouting")
    .SetParent<Ipv4RoutingProtocol> ()
    .AddConstructor<Ipv4DeflectionRouting> ()
    .AddAttribute ("Priority",
                   "The priority of the deflection routing protocol. Can be a negative value.",
                   IntegerValue(20),
                   MakeIntegerAccessor (&Ipv4DeflectionRouting::m_priority),
                   MakeIntegerChecker<int16_t> ())
    .AddAttribute ("AllowRouteBack",
                   "Set to true to allow routing packets back to its incoming interfaces; false otherwise.",
                   BooleanValue (true),
                   MakeBooleanAccessor (&Ipv4DeflectionRouting::m_allowRouteBack),
                   MakeBooleanChecker ())
    .AddTraceSource ("DeflectionTrace", 
                     "Trace source for capturing deflection events",
                     MakeTraceSourceAccessor (&Ipv4DeflectionRouting::m_deflectionTrace))
    ;
  return tid;
}

Ipv4DeflectionRouting::Ipv4DeflectionRouting (void)
{
}

Ptr<Ipv4Route> 
Ipv4DeflectionRouting::LookupPreferredRoute (Ptr<Packet> p, const Ipv4Header &header, Ptr<NetDevice> oif, Socket::SocketErrno &sockerr)
{
  NS_LOG_FUNCTION (p << header << oif << sockerr);

  // prepare for the recurrence calls
  RememberPacket (p);
  Ptr<Ipv4Route> rtentry = m_ipv4->
    GetRoutingProtocol ()->
    RouteOutput (p, header, oif, sockerr);
  ForgetPacket (p);
  NS_LOG_LOGIC ("Obtained a route = " << rtentry);

  return rtentry;
}

Ptr<Ipv4Route> 
Ipv4DeflectionRouting::LookupPreferredRoute (
    Ptr<Packet> p, const Ipv4Header &header, Ptr<const NetDevice> idev, 
    UnicastForwardCallback ucb, MulticastForwardCallback mcb, 
    LocalDeliverCallback lcb, ErrorCallback ecb)
{
  // prepare for the recurrence calls
  //
  // create a functor to get the route returned by other routing protocol
  // ...
  UcbRouteGetter routeGetter;
  // ...
  // remember this packet is now being processed, and thus recurrence calls
  // will be ended correctly
  // ...
  UnicastForwardCallback _ucb = MakeCallback (&UcbRouteGetter::Ucb, &routeGetter);
  RememberPacket (p);  
  bool routeFound = m_ipv4->
    GetRoutingProtocol ()->
    RouteInput (p, header, idev, 
    // UnicastForwardCallback
    _ucb, 
    // MulticastForwardCallback
    mcb,  
    // LocalDeliverCallback
    lcb,  
    // ErrorCallback
    ecb);
  // ...
  // forget this packet after doing the recurrence calls
  // ...
  ForgetPacket (p);
  // ...
  // set the rtentry and continue the normal RouteInput process
  Ptr<Ipv4Route> rtentry;
  if (routeFound) 
    rtentry = routeGetter.route;
  else
    rtentry = 0;
  NS_LOG_LOGIC ("Obtained a route = " << rtentry);

  return rtentry;
}

// copied and pasted from Ipv4GlobalRouting
Ptr<Ipv4Route>
Ipv4DeflectionRouting::RouteOutput (
  Ptr<Packet> p, const Ipv4Header &header, 
  Ptr<NetDevice> oif, Socket::SocketErrno &sockerr)
{
  NS_LOG_FUNCTION (this << p << header.GetSource () << oif << sockerr);

  // set the ending condition for recurrence calls 
  if (IsInProcess (p))
  {
    NS_LOG_LOGIC ("Exit immediately as this is a recurrence calling");
    return 0; // Let other routing protocols try to handle this
  }

//
// First, see if this is a multicast packet we have a route for.  If we
// have a route, then send the packet down each of the specified interfaces.
//
  if (header.GetDestination().IsMulticast ())
    {
      NS_LOG_LOGIC ("Multicast destination-- returning false");
      return 0; // Let other routing protocols try to handle this
    }
//
// See if this is a unicast packet we have a route for.
//
  NS_LOG_LOGIC ("Unicast destination- looking up");
  // lookup the preferred exit route
  Ptr<Ipv4Route> rtentry = LookupPreferredRoute (p, header, oif, sockerr);
  // lookup the actual exit route, including the possiblity of deflection
  rtentry = LookupExitRoute (rtentry, 0, header, p);

  if (rtentry)
    {
      sockerr = Socket::ERROR_NOTERROR;
    }
  else
    {
      sockerr = Socket::ERROR_NOROUTETOHOST;
    }
  return rtentry;
}

// copied and pasted from Ipv4GlobalRouting
bool 
Ipv4DeflectionRouting::RouteInput (
  Ptr<const Packet> _p, const Ipv4Header &ipHeader, Ptr<const NetDevice> idev,                             
  UnicastForwardCallback ucb, MulticastForwardCallback mcb,
  LocalDeliverCallback lcb, ErrorCallback ecb) 
{ 
  Ptr<Packet> p = _p->Copy ();
  NS_LOG_FUNCTION (this << p << ipHeader << ipHeader.GetSource () << ipHeader.GetDestination () << idev);

  // set the ending condition for recurrence calls
  if (IsInProcess (p))
  {
    NS_LOG_LOGIC ("Exit immediately as this is a recurrence calling");
    return false; // Let other routing protocols try to handle this
  }

  if (ipHeader.GetDestination ().IsMulticast ())
    {
      NS_LOG_LOGIC ("Multicast destination-- returning false");
      return false; // Let other routing protocols try to handle this
    }

// This is a unicast packet.  Check to see if we have a route for it.
//
  NS_LOG_LOGIC ("Unicast destination- looking up");
  // lookup the preferred exit route
  Ptr<Ipv4Route> rtentry = LookupPreferredRoute (p, ipHeader, idev,
                                                 ucb, mcb, lcb, ecb
                                                 );
  // lookup the actual exit route, including the possiblity of deflection
  rtentry = LookupExitRoute (rtentry, idev, ipHeader, p);

  if (rtentry != 0)
    {
      NS_LOG_LOGIC ("Found unicast destination- calling unicast callback");
      ucb (rtentry, p, ipHeader);
      return true;
    }
  else
    {
      NS_LOG_LOGIC ("Did not find unicast destination- returning false");
      return false; // Let other routing protocols try to handle this
                    // route request.
    }
}

bool 
Ipv4DeflectionRouting::IsQueueFull (Ptr<NetDevice> dev, Ptr<Packet> p) const
{
  NS_LOG_FUNCTION (dev << *p);

  // get the queue object from the net device 'dev'
  PointerValue queuePV;
  dev->GetAttribute ("TxQueue", queuePV);
  Ptr<Queue> queue = queuePV.GetObject ()->GetObject<Queue> ();
  // check if the current packet is going to be dropped
  bool full = queue->WillDrop (p);  
  if (full)
    NS_LOG_LOGIC ("The queue of the net device-" << dev->GetIfIndex () << " is full");

  return full;
}

NetDeviceContainer 
Ipv4DeflectionRouting::GetQueueFullNetDevices (Ptr<Packet> p) const
{
  NS_LOG_FUNCTION (*p);

  // store all the net devies whose queue are full
  NetDeviceContainer fullDevs;
  // walk through all net devices on this node, and skip the loopback
  for (uint32_t i = 1; i < m_ipv4->GetNInterfaces (); i++)
  {
    Ptr<PointToPointNetDevice> dev = DynamicCast<PointToPointNetDevice> (m_ipv4->GetNetDevice (i));
    NS_ASSERT_MSG (dev, "No valid PointToPointNetDevice is got!");
    if (IsQueueFull (dev, p))
    {
      fullDevs.Add (dev);
      NS_LOG_LOGIC ("Excluded net-device-" << dev->GetIfIndex () << " from being a candidate for random deflection");
    }
  }

  return fullDevs;
}

Ptr<Ipv4Route> 
Ipv4DeflectionRouting::LookupExitRoute (Ptr<Ipv4Route> preferredRoute, 
                                    Ptr<const NetDevice> idev,
                                    const Ipv4Header& header,
                                    Ptr<Packet> p)
{
  NS_LOG_FUNCTION (preferredRoute << idev);

  if ( IsQueueFull (preferredRoute->GetOutputDevice (), p) )
  {
    // create a container to contain all net devices that are excluded
    // from being the candidate of final exit net device
    NetDeviceContainer notDev;
    // skip all the interfaces whoes queue are full, 
    // this includes the original preferred out-going interface
    notDev.Add (GetQueueFullNetDevices (p));
    // skip also the input net device if it is given. This skipping
    // is necessary if packets are not allowed to route back to its
    // incoming interface
    if (!m_allowRouteBack && (idev != 0)) 
    {
      // search for the existing 'notDev' and see if the output queue
      // of the input net device is also full and thus is already added
      // into the 'notDev' in the previous method call
      //
      // set the flag to true if the 'idev' is already included 
      // in the 'notDev' container
      bool includedIDev = false;
      for (uint32_t i = 0; i<notDev.GetN (); i++)
      {
        if (notDev.Get (i) == idev)
        {
          includedIDev = true;
          break;
        }
      }
      // skip the 'idev' from being the candiate of deflected output,
      // by adding the 'idev' into the 'notDev' container. But this addition
      // is only done if the 'idev' indeed does not exist in the 'notDev'
      if (!includedIDev) notDev.Add (ConstCast<NetDevice> (idev));
    }
    // do random deflection
    Ptr<Ipv4Route> deflectedRoute = DoRandomDeflect (notDev, preferredRoute);
    if (deflectedRoute)
    {
      m_deflectionTrace (header, p, preferredRoute, deflectedRoute);

      NS_LOG_INFO ("Deflecting. Deflect packet-" 
        << p->GetUid () << " with route-[" 
        << *deflectedRoute << "]");
      return deflectedRoute;
    } 
    // no output net-devices have queue available to send the packet -> drop the packet
    else
    {
      NS_LOG_INFO ("Dropping. Forward packet-" << p->GetUid () << " to the preferred and queue-full route-[" << *preferredRoute << "]");
      return preferredRoute;
    }
  }
  else
  {
    NS_LOG_LOGIC ("No deflection. Forward packet-" 
      << p->GetUid () << " with route-[" 
      << *preferredRoute << "]");
    // return the original preferred route as the final exit route
    return preferredRoute;
  }
}

Ptr<Ipv4Route> 
Ipv4DeflectionRouting::DoRandomDeflect (NetDeviceContainer notDevContainer, Ptr<Ipv4Route> preferredRoute)
{
  NS_LOG_FUNCTION ("notDevContainer");

  // get the number of net devices to be excluded
  uint32_t xNumIf = notDevContainer.GetN ();
  // get the total number of interfaces on this node
  uint32_t numIf = m_ipv4->GetNInterfaces ();
  // return a null-route if all output net devices are queue-full and no valid deflection is possible
  if (numIf - xNumIf - 1 == 0)
  {
    NS_LOG_LOGIC ("No valid deflection is possible as all output net-devices are queue full! Returning null-route");
    return 0;
  }
  // Valid deflection is possible. Return a route randomly among all deflection candidates
  //
  // get an non-incoming interface randomly. Note that if the number of 
  // interfaces numIf is x, the last interface index is numIf - 1.
  uint32_t randIf = m_rand.GetInteger (1, numIf - xNumIf - 1);
  // adjust the randIf so that the excluded net devices are skipped
  //
  // the final randIf will be randIf + skipSize
  uint32_t skipSize = 0;
  for ( NetDeviceContainer::Iterator iter = notDevContainer.Begin (); 
    iter != notDevContainer.End (); 
    iter++)
  {
    if (randIf >= (*iter)->GetIfIndex ()) 
      skipSize++;
  }
  randIf += skipSize;
  // check for any possible errors
  NS_ASSERT_MSG (randIf >= 1 && randIf <= numIf, 
    "Random interface index " << randIf << " is not in a valid range");
  // obtain the node id on which this routing protocol is installed
  uint32_t nodeId = m_ipv4->GetNetDevice (0)->GetNode ()->GetId ();
  NS_LOG_LOGIC (
    "Node-" << nodeId 
    << " excluded interface(s) = " << PrintNetDeviceContainer (notDevContainer) 
    << ", #interface(s) = " << numIf 
    << ", random output interface = " << randIf);
  // create a route with the random interface index
  Ipv4RoutingTableEntry entry = 
    Ipv4RoutingTableEntry::CreateHostRouteTo (
    preferredRoute->GetDestination (), 
    GetRemoteAddress (DynamicCast<PointToPointNetDevice> (m_ipv4->GetNetDevice (randIf))),
    randIf
    );
  // create a Ipv4Route object and return it
  return GetIpv4RouteFrom (entry, preferredRoute, m_ipv4);
}

bool 
Ipv4DeflectionRouting::IsInProcess (Ptr<Packet> p) const
{
  NS_LOG_FUNCTION (p->GetUid ());

  bool returnYes = m_inProcessPacketSet.find (p->GetUid ()) != m_inProcessPacketSet.end ();
  NS_LOG_LOGIC ("Packet " << p->GetUid () << " is in process = " << returnYes);
  return returnYes;
}

void 
Ipv4DeflectionRouting::RememberPacket (Ptr<Packet> p)
{
  NS_LOG_FUNCTION (p->GetUid ());

  // true if the packet is added into the set
  bool newP = m_inProcessPacketSet.insert (p->GetUid ()).second;
  NS_ASSERT_MSG (newP, "Duplicated packet " << p->GetUid () << " found! Each packet "
    << "cannot be processed by Ipv4DeflectionRouting object for more than two time");
}

void 
Ipv4DeflectionRouting::ForgetPacket (Ptr<Packet> p)
{
  NS_LOG_FUNCTION (p->GetUid ());

  // 'count' stores the number of elements removed from the in-process-packet-set
  PacketSet_t::size_type count = m_inProcessPacketSet.erase (p->GetUid ());
  NS_ASSERT_MSG (count != 0, "Packet " << p->GetUid () 
    << " does not found! The packet is not remembered for being processed "
    << "and it is meaningless here to forget this packet");
  NS_ASSERT_MSG (count == 1, "Packet " << p->GetUid () 
    << " found to have multiple instances being remembered!");
}

int16_t 
Ipv4DeflectionRouting::GetPriority () const
{
  return m_priority;
}

void 
Ipv4DeflectionRouting::NotifyInterfaceUp (uint32_t i)
{}
void 
Ipv4DeflectionRouting::NotifyInterfaceDown (uint32_t i)
{}
void 
Ipv4DeflectionRouting::NotifyAddAddress (uint32_t interface, Ipv4InterfaceAddress address)
{}
void 
Ipv4DeflectionRouting::NotifyRemoveAddress (uint32_t interface, Ipv4InterfaceAddress address)
{}
void 
Ipv4DeflectionRouting::SetIpv4 (Ptr<Ipv4> ipv4)
{
  NS_LOG_FUNCTION(this << ipv4);

  NS_ASSERT_MSG (m_ipv4 == 0 && ipv4 != 0, "An Ipv4 object is set already");
  m_ipv4 = ipv4;
}

void 
Ipv4DeflectionRouting::UcbRouteGetter::Ucb (
  Ptr<Ipv4Route> r, Ptr<const Packet> p, const Ipv4Header &h)
{
  route = r;
}

} // namespace eecityu
} // namespace ns3
